updated: 2022-01-23_12:32:31-05:00

Schedulers

Workload: set of job descriptions
Scheduler: logic that decides when jobs run
Metric: measurement of scheduling quality

Scheduler 'algebra', given two variables, find the third
f(W,S)=M

Preemptive: When the operating system interrupts a program from running (vs. cooperative)

Workload Assumptions:

Each jobs run for the same amount of time
All jobs arrive at the same time
All jobs only use the CPU (no IO)
The runtime of each job is known

first in first out
shortest job first
shortest to completion first
round robin (preemptive time slices with quantum time slices, cyclic nature of queue)

Example: FIFO

Turnaround: Completion time - arrival time
Trace:

Example: Shortest Job First, with a big first job

What if they didn't run for the same amount of time?

FIFO:

when deciding what job to run next, choose the one with smallest run_time

Example: Shortest Time to completion first

What if jobs didn't arrive at the same time?

Not good...

Policy: switch jobs so we always run the one that will complete the quickest

STCF, great for small jobs who want to run and don't want to wait for a big job, bad for big jobs who could be continually kept on the bottom of the queue so they never run FIFO, great for bigger jobs since everyone is run in order, is not affected by smaller jobs arriving SJF, bad for big jobs if not first since they could never run and bad for small jobs because if a big job ever get's loaded they have to wait for it to be completely finished So yea, worst of both worlds

Example: Round Robin

what if we care about when a job starts?

Response time = first run - arrival time

Other schedulers have poor response time

I/O Aware

what if jobs wanted to use I/O?

MLFQ

what if the runtime of each job is NOT known?

Multi-Level Feedback Queue
General purpose scheduling

Two job types:

interactive: programs care about response time
batch: programs care about turnaround time

This solution is effectively multiple levels of round-robin

Priorities

Rule 1: If priority(A) > Priority(B), A runs
Rule 2: If priority(A) == Priority(B), A & B run in RR
Rule 3: Processes start at top priority
Rule 4: If job uses whole slice, demote process

problem: unforgiving, gaming the system, hard to tune...

How do we fix processes getting stuck at q0:
every so often we clear the queue, reschedule everything at highest priority

Lottery

Give processes lottery tickets
whoever wins runs
higher priority = more tickets

int counter = 0;  
int winner = getrandom(0, totaltickets);  
node_t *current = head;  
while(current) {   
	counter += current->tickets;   
	if (counter > winner) break;   
	current = current->next;   
} // current is the winner

Winner = 102